#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<time.h>
#include<stdlib.h>

void Swap(int& x, int& y)
{
	int tmp = x;
	x = y;
	y = tmp;
}


void Print_arr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		std::cout << arr[i] << " ";
	}
}


void Bubble_Sort(int* arr,int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = 1;
		for (int j = i; j < n; j++)
		{
			//假设有序
			
			if (arr[i] > arr[j])
			{
				Swap(arr[i] , arr[j]);
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}



void Insert_Sort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end>=0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}


//普通增量希尔排序
void Shell_Sort1(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i + gap < n; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}		
}


void Select_Sort01(int* arr, int n)
{
	int begin = 0;
	int min = begin;
	while (begin < n - 1)
	{
		min = begin;
		for (int i = begin+1; i < n; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;
			}
		}
		Swap(arr[begin], arr[min]);
		begin++;
	}
}



void Select_Sort02(int* arr, int n)
{
	int begin = 0, end = n - 1;
	int max = begin, min = begin;
	while (begin < end) 
	{
		for (size_t i = begin+1; i <= end; i++)
		{
			if (arr[max] < arr[i]) {
				max = i;
			}
			if (arr[min] > arr[i])
			{
				min = i;
			}
		}
		if (end == min)
		{
			max = min;
		}
		Swap(arr[begin], arr[min]);
		Swap(arr[end], arr[max]);
		begin++;
		end--;
	}
}

	
//Sedgewick增量序列
void Shell_Sort2(int* arr, int n)
{
	int arr1[] = {36289,16001,8929,3905,2161,929,505,209,109,41,19,5,1,0 };
	int gap = arr1[0];
	int j = 0;
	while (gap >= 1)
	{
		for (int i = 0; i + gap < n; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
		j++;
		gap = arr1[j];
	}
}



#define N 100000
int main()
{
	srand(time(NULL));
	//int* arr1 = (int*)malloc(sizeof(int) * N);
	//int* arr2 = (int*)malloc(sizeof(int) * N);
	int* arr3 = (int*)malloc(sizeof(int) * N);
	int* arr4 = (int*)malloc(sizeof(int) * N);
	int* arr5 = (int*)malloc(sizeof(int) * N);
	int* arr6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		int num = rand() ;
		//arr1[i] = num;
		//arr2[i] = num;
		arr3[i] = num;
		arr4[i] = num;
		arr5[i] = num;
		arr6[i] = num;

	}

	//int begin1 = clock();
	//Bubble_Sort(arr1,N);
	////Print_arr(arr1, N);
	//int end1 = clock();


	//int begin2 = clock();
	//Insert_Sort(arr2, N);
	////Print_arr(arr2, N);
	//int end2 = clock();


	int begin3 = clock();
	Shell_Sort1(arr3, N);
	//Print_arr(arr3, N);
	int end3 = clock();


	int begin4 = clock();
	Select_Sort01(arr4, N);
	//Print_arr(arr4, N);
	int end4 = clock();

	int begin5 = clock();
	Shell_Sort2(arr5, N);
	//Print_arr(arr3, N);
	int end5 = clock();

	int begin6 = clock();
	Select_Sort02(arr6, N);
	//Print_arr(arr3, N);
	int end6 = clock();




	//std::cout << end1 - begin1 << std::endl;
	//std::cout << end2 - begin2 << std::endl;
	std::cout << end3 - begin3 << std::endl;
	std::cout << end5 - begin5 << std::endl;
	std::cout << end4 - begin4 << std::endl;
	std::cout << end6 - begin6 << std::endl;


	return 0;
}


//int main()
//{
//	int arr[] = {  };
//	Select_Sort02(arr, );
//	Print_arr(arr, );
//	return 0;
//}